package count_sort

import (
	//"log"
)

//CountSort 算数排序
//最坏：O(n+k)，平均：O(n+k)， 最好：O(n+K)
//空间复杂度：O(n+k)
//稳定的排序
func CountSort(nums []int) []int {
	ln := len(nums)
	if ln < 2 {
		return nums
	}
	min := getMinElement(nums)
	max := getMaxElement(nums)
	countMap := make([]int, max-min+1)
	for _, v := range nums {
		countMap[v-min]++
	}
	sortedNums := []int{}
	for num, c := range countMap {
		for i := 0; i < c; i++ {
			sortedNums = append(sortedNums, num+min)
		}
	}
	return sortedNums;
}

func getMinElement(nums []int) int {
	min := nums[0];
	for _, v := range nums {
		if min > v {
			min = v
		}
	}
	return min
}

func getMaxElement(nums []int) int {
	max := nums[0]
	for _, v := range nums {
		if max < v {
			max = v
		}
	}
	return max
}